package top.fengleifeng.question;

import java.util.Arrays;
import java.util.Objects;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年11月25日 11:30 上午
 */
public class Num1370上升下降字符串 {

    //解法1
//    class Solution {
//
//        public String sortString(String s) {
//            if (s == null || s.length() <= 0) {
//                return s;
//            }
//            char[] chars = s.toCharArray();
//            Arrays.sort(chars);
//            int count = chars.length;
//            StringBuffer sb = new StringBuffer("");
//            while (count != 0) {
//                char min = '~';
//                for (int i = 0; i < chars.length; i++) {
//                    if (chars[i] != '?') {
//                        if (min == '~') {
//                            min = chars[i];
//                            sb.append(chars[i]);
//                            count--;
//                            chars[i] = '?';
//                        } else {
//                            if (chars[i] == min) {
//                                continue;
//                            } else {
//                                sb.append(chars[i]);
//                                count--;
//                                min = chars[i];
//                                chars[i] = '?';
//                            }
//                        }
//                    }
//                }
//                char max = '~';
//                for (int i = chars.length - 1; i >= 0; i--) {
//                    if (chars[i] != '?') {
//                        if (max == '~') {
//                            sb.append(chars[i]);
//                            count--;
//                            max = chars[i];
//                            chars[i] = '?';
//                        } else {
//                            if (chars[i] == max) {
//                                continue;
//                            } else {
//                                sb.append(chars[i]);
//                                count--;
//                                max = chars[i];
//                                chars[i] = '?';
//                            }
//                        }
//                    }
//                }
//            }
//            return sb.toString();
//        }
//    }
    //解法2 桶计算`
    class Solution {

        public String sortString(String s) {
            char[] chars = s.toCharArray();
            int[] letterArr = new int[26];
            for (int i = 0; i < chars.length; i++) {
                letterArr[chars[i] - 'a']++;
            }
            StringBuffer sb = new StringBuffer("");
            while (sb.length() != s.length()) {
                for (int i = 0; i < letterArr.length; i++) {
                    if (letterArr[i] != 0) {
                        letterArr[i] --;
                        sb.append((char) ('a' + i));
                    }
                }
                for (int i = letterArr.length-1; i >=0; i--) {
                    if (letterArr[i] != 0) {
                        letterArr[i] --;
                        sb.append((char) ('a' + i));
                    }
                }
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        String string = new Num1370上升下降字符串().new Solution().sortString("aaabbbccc");
        System.out.println(string);
    }
}
